package Data_Structure.Tree.SearchTree;

/**
 * @className: SearchTree
 * @author: 芃
 * @description: 二叉搜索树
 * @date: 2023/8/20 17:52
 */
//左节点的值均小于root，右节点的值均大于root
class Node{
    public int val;
    public Node left;
    public Node right;

    public Node(int val) {
        this.val = val;
    }
}
public class SearchTree {
    public Node root = null;

    //二叉搜索树的查找
    public Node search(int key){
        Node cur = root;
        while (cur != null){
            if (cur.val < key){//如果小于 就去右树找
                cur = cur.right;
            }else if (cur.val > key){//如果大于 就去左树找
                cur = cur.left;
            }else {//等于key的时候说明找到了
                return cur;
            }
        }
        //走到这 说明树里面没找到 返回null即可
        return null;
    }

    //二叉搜索树的插入-对于二叉搜索树来说，里面存放的数据唯一
    //对于二叉搜索树来说，插入的数据一定是在叶子结点的
    public boolean insert(int val){
        Node node = new Node(val);
        if (root == null){
            root = node;
            return true;
        }
        Node cur = root;
        Node parent = null;
        while (cur != null){
            parent = cur;
            if (cur.val > val){
                cur = cur.left;
            }else if (cur.val == val){
                return false;
                //或则抛出异常
                //throw new RuntimeException("数据重复，无法插入");
            }else {
                cur = cur.right;
            }
        }
        if (parent.val < val){
            parent.right = node;
        }else {
            parent.left = node;
        }
        return true;
    }
    //二叉搜索树的删除
    public boolean remove(int val){
        //先在二叉搜索树当中找到这个节点
        Node cur = root;
        Node parent = null;
        while (cur != null){
            if (cur.val == val){
                removeNode(cur,parent);
                return true;
            }else if (cur.val < val){
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }
        //走到这，说明没删除，即没找到
        return false;
    }
    //使用这个函数处理删除
    public void removeNode(Node cur,Node parent){
        if (cur.left == null){//cur的左树为空
            if (cur == root){
                //待删除节点为root节点
                root = cur.right;
            }else if (cur == parent.left){//cur不是root，cur是parent.left，则parent.left = cur.right
                parent.left = cur.right;//将parent的左指向cur的右
            }else {//cur不是root，cur是parent.right，则parent.right = cur.right
                parent.right = cur.right;//将parent的右指向cur的右
            }
        }else if (cur.right == null){//cur的右树为空
            if (cur == root){
                //待删除节点为root节点
                root = cur.left;
            }else if (cur == parent.left){//cur不是root，cur是parent.left，则parent.left = cur.left；
                parent.left = cur.left;//将parent的左指向cur的左
            }else { //cur不是root，cur是parent.right，则parent.right = cur.left
                parent.right = cur.left;//将parent的右指向cur的左
            }
        }else {//cur的左右都不为空
            //替罪羊法
            //找左树的最大值放到该位置，或者找到右树的最小值放到该位置
            //将待删除节点的值和替罪羊节点的值互换
            //互换完成后，因为是最大最小值，就转变成上述两种情况了
            Node ta = cur.right;//以此去寻找替罪羊节点
            Node tap = cur;
            //我们此处采用去找右树的最小值
            while (ta.left != null){
                tap = ta;
                ta = ta.left;
            }
            //当ta为空时，说明我们找到了右数的最小值
            //先交换ta和cur的值
            int val = cur.val;
            cur.val = ta.val;
            ta.val = val;
            if (ta != tap.left){
                //特殊情况，ta一步都没走，即ta的左树本来就为空
                tap.right = ta.right;
            }else {
                //交换完成后，就转换成上述删除时左树为空的情况了
                //上述第一种情况，cur.left == null
                //cur = parent.left
                tap.left = ta.right;
            }

        }
    }

    //中序遍历这颗二叉树
    public void inOrder(Node root){
        if (root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
}
